package leetcode.N401_N500;

public class N456 {

    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        System.out.println(find132patternV3(nums));
    }

    static boolean find132pattern(int[] nums) {
        if (nums.length < 3) {
            return false;
        }
        int length = nums.length;
        // 记录当前下表前 最小的一个元素的值
        int[] down = new int[length];
        // 记录当前下表 到上一个最小值之间的最大值
        int[] up = new int[length];

        int min = nums[0];
        int max = nums[0];
        for (int i = 1; i < length; i++) {
            if (nums[i - 1] < min) {
                min = down[i] = nums[i - 1];
                max = up[i] = nums[i - 1];
            } else {
                down[i] = min;
                if (nums[i - 1] > max) {
                    max = up[i] = nums[i - 1];
                } else {
                    up[i] = max;
                }
            }
        }
        for (int i = length - 1; i > 0; i--) {
            for (int k = 1; k <= i; k++) {
                if (nums[i] < up[k] && nums[i] > down[k]) {
                    return true;
                }
            }
        }
        return false;
    }

    static boolean find132patternV2(int[] nums) {
        int len = nums.length;
        int top = len;
        int[] stack = new int[len];
        int second = Integer.MIN_VALUE;
        for (int i = len - 1; i >= 0; i--) {
            if (nums[i] < second) {
                return true;
            }
            while (top < len && stack[top] < nums[i]) {
                second = stack[top++];
            }
            stack[--top] = nums[i];
        }
        return false;
    }

    static boolean find132patternV3(int[] nums) {

        int length = nums.length;
        int second = Integer.MIN_VALUE;
        int[] stack = new int[length];
        int index = 0;

        for (int i = length - 1; i >= 0; i--) {
            if (nums[i] < second) {
                return true;
            }
            while (index > 0 && nums[i] > stack[index - 1]) {
                second = stack[--index];
            }
            stack[index++] = nums[i];
        }
        return false;
    }

}
